class Solution {

    int arr[10010] = { 0 };
public:
    int deleteAndEarn(vector<int>& nums) {

        map<int, int> my_map;

        for (auto num : nums)
            my_map[num]++;

        int num_max = nums[0];

        for (auto x : my_map)
        {
            int num = x.first, cnt = x.second;

            arr[num] = num * cnt;

            num_max = num;
        }

        int n = num_max;

        vector<int> dp(n + 3, 0);

        for (int i = 2; i <= n + 2; i++)
        {
            dp[i] = max(dp[i - 1], dp[i - 2] + arr[i - 2]);
        }

        return dp[n + 2];
    }
};